home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part1 / 5954 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  2.8 KB
  1. Path: pegasus.montclair.edu!harmon
  2. From: harmon@pegasus.montclair.edu (Derek Harmon)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: unique id for a string
  5. Date: 18 Feb 1996 17:20:46 -0500
  6. Organization: Montclair State University
  7. Message-ID: <harmon.824680556@pegasus.montclair.edu>
  8. References: <1996Feb16.175601.114182@kuhub.cc.ukans.edu>
  9. NNTP-Posting-Host: pegasus.montclair.edu
  10. X-Newsreader: NN version 6.5.0 #68 (NOV)
  11.  
  12. anh@kuhub.cc.ukans.edu writes:
  13. >This is not a quite a C problem. But since the implementation will be in 
  14. >C anyway.
  15.  
  16.    Then I won't quite give an answer in C.  :)
  17.  
  18. >Given an alphabet, for example, E = {A-Z}, I need to assign an unique id 
  19. >to each possible strings (finite, approx 32 chars long, or whatever, but 
  20. >it is finite) formed by the letters from E. I would like the id to be as 
  21. >small as possible. Is there a good formula?
  22.  
  23. >HELLO =  H * 26^4 + E * 26 ^3 +  L * 26^2 + L * 26^1 + E * 26^0
  24.   
  25.    If the possible strings had to be English, a slight improvement (smaller
  26. id for more strings) could be attained by ordering the ASCII char values to
  27. alternate values for the corresponding character which are used less in the
  28. language (ie, vowels would be ASCII 1-5, S could be 6, and X could be 26).
  29.  
  30. >But the id is way too big. I need something that fits within a 32-bits int 
  31. >or a 64-bits long.
  32.  
  33. >Another way is to simply assign a id to a word and store the word in a 
  34. >binary search tree, and therefore, it is relatively fast to make sure 
  35. >each word has an unique id. But I think it is still to slow. We are 
  36. >talking about a possible 200,000+ words.
  37.  
  38.    How balanced the tree would be depends on either the order of input, or
  39. the tree's self-balancing of itself which makes input longer, but logarith-
  40. mically lowers the bound on search time.  But we are talking about more than
  41. 200,000 words here, and that is where the problem occurs.  If the max length
  42. of these strings is 32 characters, then we are talking about roughly 7.3 x
  43. 10^43 different strings.  That will not fit into a 64-bit long.  :)
  44.  
  45.    The formula you give above will give all those strings distinct id nums,   
  46. if you have knowledge of the probability of occurence of symbols from that
  47. language, you can shift the probability of smaller id num size (there will
  48. still be large id nums) for a random sampling of those strings.  However,
  49. if symbols have equal probabilities of selection, finnagling of the formula
  50. won't add any advantage.  If it were possible, the world would be a path to
  51. your door for an infinite data compression method.
  52.  
  53.                                                     -- Stone
  54. --
  55. # Derek Harmon (aka Stonelight)    harmon@pegasus.montclair.edu
  56. # - Computer Science Undergrad, Montclair State University, NJ
  57. # - My views are my own, nobody else is this creative.  3;)>
  58. ... Recursive. adj., see Recursive.
  59.  
  60.